package bank;

import java.util.Arrays;

public class _31NextPermutation {
    public static void nextPermutation(int[] nums) {
        //  从右到左寻找第一个下降点
        int index = 0;
        for (int i = nums.length - 1;i > 0;i--){
            if (nums[i] > nums[i-1]){
                //  i-1
                index = i - 1;
                break;
            }
            if (i - 1 == 0 && nums[i] < nums[i-1]){
                Arrays.sort(nums);
                return;
            }
        }
        for (int i = nums.length - 1;i > index;i--){
            //  从右开始寻找第一个比nums[index]大的元素
            if (nums[i] > nums[index]){
                swap(nums,i,index);
                //  对index右侧的元素排序
                reverse(nums,index);
                break;
            }
        }
    }

    private static void reverse(int[] nums, int index) {
        int left = index + 1,right = nums.length - 1;
        while (left < right){
            swap(nums,left++,right--);
        }
    }

    private static void swap(int[] nums, int i, int index) {
        int temp = nums[i];
        nums[i] = nums[index];
        nums[index] = temp;
    }
}
